package com.klun.likou;

import org.apache.commons.lang.StringUtils;

import java.util.*;

public class Solution15 {

	public static void main(String[] args) {
		int[] nums = {-1, 0, 1, 2, -1, -4};
		//            -4  -1 -1  0   1   2
		//            0   1  2  3   4   5
		List<List<Integer>> lists = threeSum(nums);
		for (List<Integer> list : lists) {
			for (Integer integer : list) {
				System.out.print(integer + ",");
			}
			System.out.println();
		}
	}

	/**
	 * 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c
	 * 得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
	 *
	 * @return
	 */
	public static List<List<Integer>> threeSum(int[] nums) {
		Arrays.sort(nums); // 排序 + 包含坐标信息
		List<List<Integer>> result = new ArrayList<>();
		Map<Integer, String> map = new HashMap<>();
		for (int i = 0; i < nums.length; i++) {
			for (int j = i + 1; j < nums.length; j++) {
				int key = nums[i] + nums[j];
				String s = map.get(key);
				if (null == s) {
					map.put(key, i + "," + j);
				} else {
					map.put(key, s + ";" + i + "," + j);
				}
			}
		}
		for (int i = 0; i < nums.length; i++) {
			int num = nums[i];
			String s = map.get(-num);
			if (null != s) {
				String[] split = s.split(";");
				for (String s1 : split) {
					List<Integer> list = new ArrayList<>();
					String[] split1 = s1.split(",");
					Integer i1 = Integer.valueOf(split1[0]);
					Integer i2 = Integer.valueOf(split1[1]);
					if (i >= i1 || i >= i2) {
						continue;
					}
					int num1 = nums[i1];
					int num2 = nums[i2];
					list.add(num);
					list.add(num1);
					list.add(num2);
					result.add(list);
					System.out.println(i + i1 + i2 +"");
				}
			}
		}
		return result;
	}
}